#include "big_int.h"

big_int :: big_int(std :: string s)
{
   int k = s.size() % base_lenght;
   for (int i = s.size(); i - base_lenght >= 0; i -= base_lenght)
   {
      digits.push_back(atoi(s.substr(i - base_lenght, base_lenght).c_str()));
   }
   if (k != 0)
      digits.push_back(atoi(s.substr(0, k).c_str()));
}

int big_int :: compare_to(const big_int& x, int shift) const
{
   int cur_size = digits.size();
   int x_size = x.digits.size();

   if (cur_size - x_size - shift != 0)
      return cur_size - x_size - shift;
   for (int i = x_size - 1; i >= 0; i--)
   {
      if (digits[shift + i] != x.digits[i])
         return digits [shift + i] - x.digits[i];
   }
   return 0;
}

void big_int :: cut_zeros()
{
   while ((digits.size() > 1) && (digits.back() == 0))
      digits.pop_back();
}

int big_int :: find_quot(const big_int& x, int shift) const
{
   if (compare_to(x, shift) < 0)
      return 0;
   int m, l = 0;
   int r = base;

   while (l + 1 != r)
   {
      m = (l + r) / 2;
      if (compare_to(x * m, shift) < 0)
         r = m;
      else
         l = m;
   }
   return l;
}

big_int big_int :: multiply(int &x) const
{
   int carry = 0;
   big_int res = *this;
   int n = res.digits.size();
   for (int i = 0; i < n; i++)
   {
      long long t = res.digits[i] * 1ll * x + carry;
      res.digits[i] = static_cast <int> (t % base);
      carry = static_cast <int> (t / base);
   }
   if (carry != 0)
      res.digits.push_back(carry);
   res.cut_zeros();
   return res;
}
big_int big_int :: operator *(int &x) const
{
   big_int res = *this;
   return res.multiply(x);
}

big_int big_int :: subtract(const big_int& x, int shift) const
{
   int x_size = x.digits.size();
   big_int res = *this;

   if (res.compare_to(x, shift) < 0)
      return res;

   for (int i = 0; i < x_size; i++)
   {
      res.digits[i + shift] -= x.digits[i];
      size_t k = i;

      while ((res.digits[k + shift] < 0) && (k < res.digits.size()))
      {
         res.digits[k + shift] += base;
         res.digits[k + shift + 1]--;
         k++;
      }
      res.cut_zeros();
   }
   return res;
}

std :: pair<big_int, big_int> big_int :: divide(const big_int& x) const
{
   big_int a = *this;
   int shift = a.digits.size() - x.digits.size();
   std :: pair<big_int, big_int> res("0", "0");
   std :: vector <int> quotient(1, 0);

   while (shift >= 0)
   {
      int quot = a.find_quot(x, shift);
      a = a.subtract(x * quot, shift--);
      quotient.push_back(quot);
   }

   std :: reverse(quotient.begin(), quotient.end());
   res.first.digits = quotient;
   res.first.cut_zeros();

   res.second = a;
   return res;
}

std :: ofstream& operator<<(std::ofstream& out, const big_int& x)
{
   int x_size = x.digits.size();
   if(x_size == 0)
      return out;
   out << x.digits[x_size - 1];
   for (int i = x_size - 2; i >= 0; i--)
   {
      int tmp = x.digits[i];
      int n = 1;
      while (tmp > x.base_lenght)
      {
         n++;
         tmp /= 10;
      }
      for (int k = n; k < x.base_lenght; k++)
         out << "0";
      out << x.digits[i];
   }
   return out;
}